package ru.ifmo.games.solvers.chinessecheckers;

import java.util.*;

/**
 * @author avhaliullin
 */
public class ChinesseCheckers {
    int maxStep = 35;

    Set<Long> used = new HashSet<Long>();

    void print(boolean[][] state) {
        System.out.println();
        for (int i = 0; i < 7; i++) {
            for (int j = 0; j < 7; j++) {
                System.out.print(checkConstraint(i, j) ? (state[i][j] ? "1" : "0") : " ");
            }
            System.out.println();
        }
    }

    boolean check(State state, int step) {
        if (step == maxStep) {
            return true;
        }
        boolean[][] cur = state.positions;
//        print(cur);
        for (int i = 0; i < 7; i++) {
            for (int j = 0; j < 7; j++) {
                if (checkConstraint(i, j)) {
                    if (defaultTrans.getVal(cur, i, j)) {
                        if (checkConstraint(i - 1, j) && checkConstraint(i + 1, j)) {
                            if (defaultTrans.getVal(cur, i + 1, j)) {
                                if (!defaultTrans.getVal(cur, i - 1, j)) {
                                    cur[i - 1][j] = true;
                                    cur[i + 1][j] = false;
                                    cur[i][j] = false;
                                    boolean bad = false;
                                    if (step < 25) {
                                        long stateLong = 0;
                                        for (Trans trans : transes) {
                                            stateLong = transposition(cur, trans);
                                            if (used.contains(stateLong)) {
                                                bad = true;
                                                break;
                                            }
                                        }
                                    }
                                    boolean res = false;
                                    if (!bad) {
                                        res = check(new State(cur, step < 25), step + 1);
                                    }
                                    cur[i - 1][j] = false;
                                    cur[i + 1][j] = true;
                                    cur[i][j] = true;
                                    if (res) {
                                        print(cur);
                                        return true;
                                    }
                                }
                            } else {
                                if (defaultTrans.getVal(cur, i - 1, j)) {
                                    cur[i - 1][j] = false;
                                    cur[i + 1][j] = true;
                                    cur[i][j] = false;
                                    boolean bad = false;
                                    if (step < 25) {
                                        long stateLong = 0;
                                        for (Trans trans : transes) {
                                            stateLong = transposition(cur, trans);
                                            if (used.contains(stateLong)) {
                                                bad = true;
                                                break;
                                            }
                                        }
                                    }
                                    boolean res = false;
                                    if (!bad) {
                                        res = check(new State(cur, step < 25), step + 1);
                                    }
                                    cur[i - 1][j] = true;
                                    cur[i + 1][j] = false;
                                    cur[i][j] = true;
                                    if (res) {
                                        print(cur);
                                        return true;
                                    }
                                }

                            }
                        }
                        if (checkConstraint(i, j - 1) && checkConstraint(i, j + 1)) {
                            if (defaultTrans.getVal(cur, i, j + 1)) {
                                if (!defaultTrans.getVal(cur, i, j - 1)) {
                                    cur[i][j - 1] = true;
                                    cur[i][j + 1] = false;
                                    cur[i][j] = false;
                                    boolean bad = false;
                                    if (step < 25) {
                                        long stateLong = 0;
                                        for (Trans trans : transes) {
                                            stateLong = transposition(cur, trans);
                                            if (used.contains(stateLong)) {
                                                bad = true;
                                                break;
                                            }
                                        }
                                    }
                                    boolean res = false;
                                    if (!bad) {
                                        res = check(new State(cur, step < 25), step + 1);
                                    }
                                    cur[i][j - 1] = false;
                                    cur[i][j + 1] = true;
                                    cur[i][j] = true;
                                    if (res) {
                                        print(cur);
                                        return true;
                                    }
                                }
                            } else {
                                if (defaultTrans.getVal(cur, i, j - 1)) {
                                    cur[i][j - 1] = false;
                                    cur[i][j + 1] = true;
                                    cur[i][j] = false;
                                    boolean bad = false;
                                    if (step < 25) {
                                        long stateLong = 0;
                                        for (Trans trans : transes) {
                                            stateLong = transposition(cur, trans);
                                            if (used.contains(stateLong)) {
                                                bad = true;
                                                break;
                                            }
                                        }
                                    }
                                    boolean res = false;
                                    if (!bad) {
                                        res = check(new State(cur, step < 25), step + 1);
                                    }
                                    cur[i][j - 1] = true;
                                    cur[i][j + 1] = false;
                                    cur[i][j] = true;
                                    if (res) {
                                        print(cur);
                                        return true;
                                    }
                                }

                            }
                        }

                    }
                }
            }
        }
        return false;
    }

    public void run() {
        BitSet set = new BitSet();
        boolean[][] start = new boolean[7][7];
        for (int i = 0; i < 7; i++) {
            for (int j = 0; j < 7; j++) {
                if (i != 4 || j != 6) {
                    start[i][j] = true;
                }
            }
        }
        check(new State(start, true), 0);
    }

    boolean checkConstraint(int i, int j) {
        if (i < 0 || i > 6) {
            return false;
        }
        if (i == 0 || i == 6) {
            return j > 1 && j < 5;
        } else {
            if (i <= 1 || i >= 5) {
                return j >= 1 && j <= 5;
            } else {
                return j >= 0 && j <= 6;
            }
        }
    }

    public static void main(String[] args) {
        new ChinesseCheckers().run();
    }

    public static final List<Trans> transes;

    public static Trans defaultTrans;

    static {
        transes = new ArrayList<Trans>();
        transes.add(new Trans() {
            public boolean getVal(boolean[][] array, int i, int j) {
                return array[i][j];
            }
        });
        transes.add(new Trans() {
            public boolean getVal(boolean[][] array, int i, int j) {
                return array[6 - i][j];
            }
        });
        transes.add(new Trans() {
            public boolean getVal(boolean[][] array, int i, int j) {
                return array[i][6 - j];
            }
        });
        transes.add(new Trans() {
            public boolean getVal(boolean[][] array, int i, int j) {
                return array[6 - i][6 - j];
            }
        });

        transes.add(new Trans() {
            public boolean getVal(boolean[][] array, int i, int j) {
                return array[j][i];
            }
        });
        transes.add(new Trans() {
            public boolean getVal(boolean[][] array, int i, int j) {
                return array[6 - j][i];
            }
        });
        transes.add(new Trans() {
            public boolean getVal(boolean[][] array, int i, int j) {
                return array[j][6 - i];
            }
        });
        transes.add(new Trans() {
            public boolean getVal(boolean[][] array, int i, int j) {
                return array[6 - j][6 - i];
            }
        });
        defaultTrans = transes.get(0);
    }

    long transposition(boolean[][] state, Trans trans) {
        long res = 0;
        for (int i = 0; i < 1; i++) {
            for (int j = 2; j < 5; j++) {
                res *= 2;
                if (trans.getVal(state, i, j)) {
                    res++;
                }
            }
        }
        for (int i = 1; i < 2; i++) {
            for (int j = 1; j < 6; j++) {
                res *= 2;
                if (trans.getVal(state, i, j)) {
                    res++;
                }
            }
        }
        for (int i = 2; i < 5; i++) {
            for (int j = 0; j < 7; j++) {
                res *= 2;
                if (trans.getVal(state, i, j)) {
                    res++;
                }
            }
        }
        for (int i = 5; i < 6; i++) {
            for (int j = 1; j < 6; j++) {
                res *= 2;
                if (trans.getVal(state, i, j)) {
                    res++;
                }
            }
        }
        for (int i = 6; i < 7; i++) {
            for (int j = 2; j < 5; j++) {
                res *= 2;
                if (trans.getVal(state, i, j)) {
                    res++;
                }
            }
        }
        return res;
    }

    class State {

        boolean[][] positions;

        public State(boolean[][] positions, boolean cache) {
            this.positions = positions;
//            for (Trans trans : transes) {
//                used.add(transposition(positions, trans));
//            }
            if (cache) {
                used.add(transposition(positions, defaultTrans));
            }
        }

    }

    interface Trans {
        public boolean getVal(boolean[][] array, int i, int j);
    }
}
